Hình học của tính khả thi
Với bài toán lồi có các ràng buộc đẳng thức $Ax=b$, một vectơ $v \in \mathbf{R}^n$ là một hướng khả thi nếu $Av = 0$. Điều này nghĩa là di chuyển theo hướng $v$ sẽ duy trì ràng buộc: $A(x+v) = b$ nếu $Ax=b$.
Để $x^*$ là điểm tối ưu, đạo hàm theo hướng $\nabla f(x^*)^T v$ phải bằng 0 với mọi hướng khả thi $v$ trong không gian nghiệm $\mathcal{N}(A)$. Điều này ngụ ý rằng gradient $\nabla f(x^*)$ phải vuông góc với $\mathcal{N}(A)$, dẫn đến sự tồn tại của các thừa số Lagrange.
Một điểm $x^*$ là tối ưu nếu và chỉ nếu tồn tại một vectơ $\nu^* \in \mathbb{R}^p$ sao cho:
$\nabla f(x^*) + A^T \nu^* = 0$
Điều này tạo thành một hệ phương trình tuyến tính đặc trưng cho sự cân bằng giữa sự giảm của hàm mục tiêu và mặt ràng buộc.
Gradient chiếu
Phép chiếu phép chiếu Euclid của gradient âm $-\nabla f(x)$ lên không gian nghiệm $\mathcal{N}(A)$ được xác định bởi:
$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$
Vectơ này biểu diễn hướng giảm khả thi "tốt nhất". Quan trọng là, $x$ là tối ưu nếu và chỉ nếu $\Delta x_{\text{pg}} = 0$.
Hệ thống KKT và các tính chất ma trận
Chúng ta có thể giải đồng thời cho bước Newton và các biến đối ngẫu bằng cách sử dụng hệ khối:
$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$Lưu ý về tính chất phổ của ma trận: Ma trận KKT là đối xứng nhưng không xác định. Nếu ma trận khả nghịch, nó có đúng $n$ giá trị riêng dương và $p$ giá trị riêng âm. Điều này ngụ ý rằng điểm tối ưu $(x^*, \nu^*)$ là một điểm yên ngựa của hàm Lagrangian $L(x, \nu) = f(x) + \nu^T(Ax-b)$, chứ không phải là một cực tiểu cục bộ đơn giản trong không gian nguyên – đối ngẫu kết hợp.